#include "sort.h"
static void partSort1(int* arr, int left, int right);
static void partSort2(int* arr, int left, int right);
static void partSort3(int* arr, int left, int right);
static void IntroSort(int* arr, int depth, int FalutPath, int left, int right);
static void _mergesort(int* arr, int* arr_cp, int left, int right);
static void HeapDown(int* arr, int node_i, int size);

void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
	return;
}
//冒泡排序
bool BubleSort(int* arr, int size)
{
	if (!arr)
		return false;
	for (int end = size; end > 1; --end)
	{
		bool flag = true;
		for (int begin = 0; begin + 1 < end; ++begin)
		{
			if (arr[begin] > arr[begin + 1])
			{
				flag = false;
				Swap(&arr[begin], &arr[begin + 1]);
			}
			else
				continue;
		}
		if (flag == true)
			return true;
	}
	return true;
}

//插入排序
bool InsertSort(int* arr, int size)
{
	if (!arr)
		return false;
	for (int begin = 1;begin < size; ++begin)
	{
		int key = arr[begin];
		int cur = begin - 1;
		while (cur >= 0)
		{
			if (key < arr[cur])
			{
				arr[cur + 1] = arr[cur];
				--cur;
			}
			else
				break;
		}
		arr[cur + 1] = key;
	}
	return true;
}

//希尔排序
bool ShellSort(int* arr, int size)
{
	if (!arr)
		return false;
	int gap = size;
	while (gap > 1)
	{
		gap = gap / 3 + 1;
		//预排序,gap == 1时插入排序
		for (int i = 0; i < gap; ++i)
		{
			for (int begin = i + gap; begin < size; begin += gap)
			{
				int key = arr[begin];
				int cur = begin - gap;
				while (cur >= i)
				{
					if (key < arr[cur])
					{
						arr[cur + gap] = arr[cur];
						cur -= gap;
					}
					else
						break;
				}
				arr[cur + gap] = key;
			}
		}
	}
	return true;
}

//选择排序
bool SelectSort(int* arr, int size)
{
	if (!arr)
		return false;
	int left = 0, right = size - 1;
	for ( ; left < right ; ++left, --right)
	{
		int maxi = left;
		int mini = left;
		for (int i = left + 1; i <= right; ++i)
		{
			if (arr[maxi] < arr[i])
				maxi = i;

			if (arr[mini] > arr[i])
				mini = i;
		}

		Swap(&arr[left], &arr[mini]);
		if (maxi == left)
			maxi = mini;
		Swap(&arr[right], &arr[maxi]);
	}
	return true;
}
/////////////////////快排系列////////////////////////////////////////////
//三数取中
static int getkeyi(int* arr, int left, int right)
{
	int mid = (left + right) / 2;
	if (arr[left] < arr[mid])
	{
		if (arr[mid] < arr[right])
			return mid;
		else if (arr[left] > arr[right])
			return left;
		else
			return right;
	}
	else
	{
		if (arr[mid] > arr[right])
			return mid;
		else if (arr[right] > arr[left])
			return left;
		else
			return right;
	}
}

//快排前后指针法
void partSort1(int* arr, int left, int right)
{
	//避免最后的多次递归
	if (right - left + 1 <= 10)
	{
		InsertSort(arr + left, right - left + 1);
		return;
	}

	if (left >= right)
		return;
	int keyi = getkeyi(arr, left, right);
	Swap(&arr[left], &arr[keyi]);
	keyi = left;
	int cur = left + 1;
	int prev = left;
	int end = right;
	while (cur <= end)
	{
		if (arr[cur] < arr[keyi] && ++prev != cur)
		{
			Swap(&arr[cur], &arr[prev]);
		}
		cur++;
	}
	Swap(&arr[prev], &arr[keyi]);
	//[left, prev - 1] prev [prev + 1, right]
	partSort1(arr, left, prev - 1);
	partSort1(arr, prev + 1, right);
}

//快排hoare法
void partSort2(int* arr, int left, int right)
{
	//避免最后的多次递归
	if (right - left + 1 <= 10)
	{
		InsertSort(arr + left, right - left + 1);
		return;
	}

	if (left >= right)
		return;
	int keyi = getkeyi(arr, left, right);
	Swap(&arr[keyi], &arr[left]);
	int key = arr[left];
	keyi = left;
	int begin = left + 1;
	int end = right;
	while (begin < end)
	{
		while (begin < end && arr[end] >= key)
			--end;
		while (begin < end && arr[begin] <= key)
			++begin;
		Swap(&arr[begin], &arr[end]);
	}
	Swap(&arr[keyi], &arr[begin]);
	//[left, begin - 1] begin [begin + 1, right]
	partSort2(arr, left, begin - 1);
	partSort2(arr, begin + 1, right);
}

//快排优化(针对多组重复数据)
void partSort3(int* arr, int begin, int end)
{
	//避免最后的多次递归
	if (end - begin + 1 <= 10)
	{
		InsertSort(arr + begin, end - begin + 1);
		return;
	}

	if (begin >= end)
		return;
	Swap(&arr[getkeyi(arr, begin, end)], &arr[begin]);
	int key = arr[begin];
	int left = begin;
	int right = end;
	int cur = left + 1;
	while (cur <= right)
	{
		//控制left始终指向的值为key值且为首个key值
		if (arr[cur] < key)
		{
			Swap(&arr[cur], &arr[left]);
			left++;
			cur++;
		}
		else if (arr[cur] > key)
		{
			Swap(&arr[cur], &arr[right--]);
		}
		else
			cur++;
	}
	partSort3(arr, begin, left - 1);
	partSort3(arr, right + 1, end);
}

//stl快排采用自省快排	使用参数FalutPath作为最大递归深度限度,若超过则执行堆排
void IntroSort(int* arr, int depth, int FalutPath, int left, int right)
{
	depth++;
	//检查递归深度
	if (depth > FalutPath)
	{
		HeapSort(arr + left, right - left + 1);
		return;
	}
	//小区间优化
	if (right - left + 1 <= 10)
	{
		InsertSort(arr + left, right - left + 1);
		return;
	}
	if (left >= right)
		return;
	int keyi = getkeyi(arr, left, right);
	Swap(&arr[keyi], &arr[left]);
	keyi = left;
	int key = arr[keyi];
	int begin = left + 1;
	int end = right;
	while (begin < end)
	{
		while (begin < end && arr[end] >= key)
			--end;
		while (begin < end && arr[begin] <= key)
			++begin;
		Swap(&arr[begin], &arr[end]);
	}
	Swap(&arr[keyi], &arr[begin]);
	IntroSort(arr, depth, FalutPath, left, begin - 1);
	IntroSort(arr, depth, FalutPath, begin + 1, right);
}



//快排
bool QuickSort(int* arr, int size)
{
	if (!arr)
		return false;

	//计算FalutPath最大递归限度
	int logN = 0;
	for (int i = 1; i < size; i *= 2)
	{
		++logN;
	}
	/*IntroSort(arr, 0, 2 * logN, 0, size - 1);*/
	partSort3(arr, 0, size - 1);
	return true;
}

//快排非递归
bool QuickSortNonR(int* arr, int size)
{
	if (!arr)
		return false;
	queue<int> qa;
	qa.push(0);
	qa.push(size - 1);
	//采用前后指针法
	while (!qa.empty())
	{
		//取出区间
		int left = qa.front();
		qa.pop();
		int right = qa.front();
		qa.pop();
		if (left >= right)
			continue;
		//三数取中
		int keyi = getkeyi(arr, left, right);
		Swap(&arr[keyi], &arr[left]);
		keyi = left;

		int end = right;
		int cur = left + 1;
		int prev = left;
		while (cur <= end)
		{
			if (arr[cur] < arr[keyi] && ++prev != cur)
			{
				Swap(&arr[prev], &arr[cur]);
			}
			cur++;
		}
		Swap(&arr[keyi], &arr[prev]);
		//入队,广度BFS [left, prev - 1] prev [prev + 1, right]
		qa.push(left);
		qa.push(prev - 1);
		qa.push(prev + 1);
		qa.push(right);
	}
	return true;
}
////////////////////////////////////////////////////////////////////////
void _mergesort(int* arr, int* arr_cp, int left, int right)
{
	if (left >= right)
		return;
	int mid = left + (right - left) / 2;
	//[left, mid - 1][mid, right]会导致死循环 栈溢出
	_mergesort(arr, arr_cp, left, mid);
	_mergesort(arr, arr_cp, mid + 1, right);
	int begin1 = left, end1 = mid;
	int begin2 = mid + 1, end2 = right;
	int index = 0;
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (arr[begin1] <= arr[begin2])
		{
			arr_cp[index++] = arr[begin1];
			begin1++;
		}
		else
		{
			arr_cp[index++] = arr[begin2];
			begin2++;
		}
	}
	while (begin1 <= end1)
	{
		arr_cp[index++] = arr[begin1];
		begin1++;
	}
	while (begin2 <= end2)
	{
		arr_cp[index++] = arr[begin2];
		begin2++;
	}
	memcpy(arr + left, arr_cp, sizeof(int) * (index));
	return;
}

//归并排序
bool MergeSort(int* arr, int size)
{
	if (!arr)
		return false;
	int* arr_cp = new int[size];
	memcpy(arr_cp, arr, size * sizeof(int));
	_mergesort(arr, arr_cp, 0, size - 1);
	delete[] arr_cp;
	return true;
}

//归并排序非递归(不借助栈和队列,使用循环)
bool MergeSortNonR(int* arr, int size)
{
	if (!arr)
		return false;
	int* arr_cp = new int[size];
	memcpy(arr_cp, arr, sizeof(int) * size);
	//将区间分成 N 组, 每组gap个成员
	int gap = 1;
	while (gap < size)
	{
		for (int i = 0;i < size;i += 2 * gap)
		{
			//记录每组排序初始位置
			int left = i;
			//更新排序区间
			int begin1 = i, end1 = i + gap - 1;
			int begin2 = i + gap, end2 = i + 2 * gap - 1;
			//1.end1 越界	2. begin2 越界 说明每组数组已排好
			//3.end2 越界 需进行修正
			int index = 0;
			if (begin2 >= size)
				break;
			if (end2 >= size)
				end2 = size - 1;
			while (begin1 <= end1 && begin2 <= end2)
			{
				if (arr[begin1] <= arr[begin2])
				{
					arr_cp[index++] = arr[begin1++];
				}
				else
				{
					arr_cp[index++] = arr[begin2++];
				}
			}
			while (begin1 <= end1)
			{
				arr_cp[index++] = arr[begin1++];
			}
			while (begin2 <= end2)
			{
				arr_cp[index++] = arr[begin2++];
			}
			memcpy(arr + left, arr_cp, sizeof(int) * index);
		}
		gap *= 2;
	}
	return true;
}
/////////////////////////////堆//////////////////////////
//堆的向下移动算法(默认当前节点的子树已为堆) 向下建堆-时间复杂度 0(N)
void HeapDown(int* arr, int node_i, int size)	//时间复杂度:O(logN)
{
	int parent = node_i;
	int child = parent * 2 + 1;
	while (child < size)
	{
		if (child + 1 < size && arr[child] < arr[child + 1])
			child += 1;
		if (arr[parent] >= arr[child])
		{
			break;
		}
		else
		{
			Swap(&arr[parent], &arr[child]);
			parent = child;
			child = parent * 2 + 1;
		}
	}
}
//堆排序
bool HeapSort(int* arr, int size)	//(建堆后使用)	降序用小堆,升序用大堆
{
	//建堆
	int node_i = (size - 1 - 1) / 2;
	while (node_i >= 0)
	{
		HeapDown(arr, node_i, size);
		node_i--;
	}
	if (!arr)
		return false;
	for (int cur = size - 1; cur > 0; --cur)
	{
		Swap(&arr[0], &arr[cur]);
		HeapDown(arr, 0, cur);
	}
	return true;
}